//  On my honor:
//	
//  - I have not used source code obtained from another student, 
//    or any other unauthorized source, either modified or unmodified.  
//	
//  - All source code and documentation used in my program 
//    is either my original work, or was derived by me from the source
//    code published in the textbook for this course.
//	
//  - I have not discussed coding details about this project with anyone
//    other than my instructor, ACM/UPE tutors or the GTAs assigned to this
//    course. I understand that I may discuss the concepts of this program
//    with other students, and that another student may help me debug my
//    program so long as neither of us writes anything during the discussion
//    or modifies any computer file during the discussion.  I have violated
//    neither the spirit nor letter of this restriction.
//	

/**
 * @author Christopher Suh, Eric Yoo
 * 
 */
public class LinkedList {

	private ListNode headNode, tailNode, curNode;

	LinkedList() {
		headNode = null;
		tailNode = null;
		curNode = null;
	}

	/**
	 * Takes in 2 values, index and size of the memory block and adds it to the
	 * LinkedList.
	 * 
	 * @param index_in
	 *            Index of the element being added.
	 * @param size_in
	 *            Size of the free block.
	 */
	public void insert(int index_in, int size_in) {
		ListNode temp = new ListNode(index_in, size_in);
		ListNode cur = headNode;
		if (headNode == null) {
			headNode = tailNode = temp;
		} else {
			while (cur != null && cur.getSize() < temp.getSize()) {
				cur = cur.getNext();
			}
			if (cur == headNode) {
				temp.setNext(headNode);
				headNode.setPrev(temp);
				headNode = temp;
			} else if (cur == null) {
				tailNode.setNext(temp);
				temp.setPrev(tailNode);
				tailNode = temp;
			} else {
				temp.setNext(cur);
				temp.setPrev(cur.getPrev());
				cur.getPrev().setNext(temp);
				cur.setPrev(temp);
			}
		}
	}

	/**
	 * Removes the smallest block that can fit the given size and return that
	 * block.
	 * 
	 * @param size_in
	 *            Minimum size of the block to be removed.
	 * @return Smallest freeblock that can fit the specified size.
	 */
	public ListNode remove(int size_in) {
		if (headNode == null)
			return null;

		ListNode cur = headNode;
		while (cur != null && cur.getSize() < size_in)
			cur = cur.getNext();

		if (cur == null)
			return null;

		return removeNode(cur);
	}

	/**
	 * Removes the specified from the list and returns the Node.
	 * 
	 * @param removed
	 *            Node to be removed.
	 * @return Removed node.
	 */
	public ListNode removeNode(ListNode removed) {
		if (removed == headNode) {
			if (headNode.getNext() != null)
				headNode.getNext().setPrev(null);
			headNode = headNode.getNext();
			removed.setNext(null);
			return removed;
		}
		if (removed == tailNode) {
			tailNode.getPrev().setNext(null);
			tailNode = tailNode.getPrev();
			removed.setPrev(null);
			return removed;
		}
		removed.getPrev().setNext(removed.getNext());
		removed.getNext().setPrev(removed.getPrev());
		removed.setNext(null);
		removed.setPrev(null);
		return removed;
	}

	/**
	 * Resets the current pointer to the head node.
	 */
	public void resetCurNode() {
		curNode = headNode;
	}

	/**
	 * Returns the next element in the list.
	 * 
	 * @return
	 */
	public ListNode getNext() {
		ListNode temp = curNode;
		if (curNode != null) {
			curNode = curNode.getNext();
		}
		return temp;
	}
}
